#include<cstdio>

const int mod=10000;

struct matrix
{
	int m[3][3];
};

matrix mul(matrix a,matrix b,int k)
{
	matrix c;
	c.m[1][1]=(a.m[1][1]*b.m[1][1]+a.m[1][2]*b.m[2][1])%k;
	c.m[1][2]=(a.m[1][1]*b.m[1][2]+a.m[1][2]*b.m[2][2])%k;
	c.m[2][1]=(a.m[2][1]*b.m[1][1]+a.m[2][2]*b.m[2][1])%k;
	c.m[2][2]=(a.m[2][1]*b.m[1][2]+a.m[2][2]*b.m[2][2])%k;
	return c;
}

matrix index;

matrix quickpow(matrix m,int n,int k)
{
	matrix b=index;
	while(n>0)
	{
		if(n&1)b=mul(b,m,k);
		n=n>>1;
		m=mul(m,m,k);
	}
	return b;
}

int main()
{
	matrix fb;
	index.m[1][1]=index.m[2][2]=1;
	index.m[1][2]=index.m[2][1]=0;
	fb.m[1][1]=fb.m[1][2]=fb.m[2][1]=1;
	fb.m[2][2]=0;
	int n;
	while(scanf("%d",&n),n>=0)
	{
		if(n==0){printf("0\n");continue;}
		matrix b=quickpow(fb,n,mod);
		printf("%d\n",b.m[2][1]);
	}
	return 0;
}
